#include "set.h"
#include <stdio.h>


struct set_data{
	Treeptr root;
/*In case I think something*/
	};

struct tnode{
	element_t data;
	Treeptr right;
	Treeptr left;
	unsigned int size;
	};
	
Treeptr insert_node(Treeptr temp, element_t data);
void clear_tree(Treeptr temp);



set create(void)
{
 set new;
 new = malloc(sizeof(struct set_data));
 if ( new == NULL) return NULL;
 new -> root = NULL;
 return new;
}



void clear(set target_set)
{
 Treeptr temp = target_set -> root;
 clear_tree(temp);
 target_set -> root = NULL;
}

void destroy(set target_set)
{
 clear(target_set);
 free(target_set);
 target_set = NULL;
}


unsigned int size(set target_set)
{
 if(target_set -> root != NULL)
	 return target_set -> root -> size;
 return 0;
}



bool insert(set target_set, element_t data)
{if(target_set == NULL)
	return false;
 target_set -> root = insert_node(target_set -> root, data);
 return true;
}


bool remove_data(set target_set, unsigned int node)
{
 Treeptr temp, parent, delete, previous;
 unsigned int current = 1;
 bool right, left;
 right = left = false;
 parent = target_set -> root;
 temp = target_set -> root;
 temp -> size--;
 if(node > size(target_set) )
	return false;
 if(temp -> left != NULL)
	current = temp -> left -> size + 1;
 while(current != node){
	if(current > node){
		parent = temp;
		temp = temp -> left;
		left = 1;
		right = 0;
		if(temp -> right != NULL)
			current -= temp -> right -> size;
		current--;
		}
	else if(current < node){
		parent = temp;
		temp = temp -> right;
		left = 0;
		right = 1;
		if(temp -> left != NULL)
			current += temp -> left -> size;
		current++;
		}
	temp -> size--;
	}
 delete  = temp;
 if(temp -> right != NULL){
 	temp = temp -> right;
	while (temp -> left != NULL){
		previous = temp;
		temp -> size--;
		temp = temp -> left;
		}
	if(right)
		parent -> right = temp;
	else
		parent -> left = temp;
	temp -> left = delete -> left;
	previous -> left = NULL;
	temp -> right = delete -> right;
	temp -> size = delete -> size ;
	}
 else if(temp -> left != NULL){
	if(right)
		parent -> right = temp -> left;
	else
		parent -> left = temp -> left;
	}
 else{
	if(right)
		parent -> right = NULL;
	else
		parent -> left = NULL;
	}
 free(delete);
 return true;
}









element_t at(set target_set, unsigned int node)
{
 Treeptr temp = target_set -> root;
 unsigned int current = 1;
 if(node > size(target_set) ){
	printf("There is no element %d in the set!\n",node);
	return;
	}
 if(temp -> left != NULL)
	current = temp -> left -> size + 1;
 while(current != node){
	if(current > node){
		temp = temp -> left;
		if(temp -> right != NULL)
			current -= temp -> right -> size;
		current--;
		}
	else if(current < node){
		temp = temp -> right;
		if(temp -> left != NULL)
			current += temp -> left -> size;
		current++;
		}
	}
 return temp -> data;
}



void clear_tree(Treeptr temp)
{
 if(temp == NULL)
	return;
 clear_tree(temp -> left);
 clear_tree(temp -> right);
 free(temp);
}



Treeptr insert_node(Treeptr temp, element_t data)
{
 if(temp == NULL){
	temp = malloc(sizeof(struct tnode));
	if(temp == NULL) return false;
	temp -> data = data;
	temp -> right = NULL;
	temp -> left = NULL;
	temp -> size = 1;
	//return temp;
	}
 else if(temp -> data > data){
	temp -> left = insert_node(temp -> left, data);
	temp -> size++;
	}
 else if(temp -> data < data){
	temp -> right = insert_node(temp -> right, data);
	temp -> size++;
	}
}

